package dp;

/**
 * 请注意区分子串和子序列的不同，给定两个字符串str1和str2，求两个字符串的最长公共子串。
 * 动态规划空间压缩的技巧讲解
 * @author Liaorun
 */
public class LeastCommonSubString {

    public static void main(String[] args) {
        System.out.println(leastCommonSubSubString("abcd", "bc"));
        System.out.println(leastCommonSubSubString2("abcd", "bc"));
    }

    /**
     * 返回两个字符串的最长公共字串
     * 没有空间压缩版本的二维动态规划解法
     *
     * @param str1 字符串
     * @param str2 字符串
     * @return 最长公共子串
     */
    public static String leastCommonSubSubString(String str1, String str2) {
        if (str1 == null || str2 == null) {
            return "";
        }

        char[] chars = str1.toCharArray();
        char[] chars2 = str2.toCharArray();

        int[][] dp = getdp(chars, chars2);

        int end = 0;
        int max = 0;
        for (int i = 0; i < chars.length; i++) {
            for (int j = 0; j < chars2.length; j++) {
                if (dp[i][j] > max) {
                    end = i;
                    max = dp[i][j];
                }
            }
        }

        return str1.substring(end - max + 1, end + 1);
    }

    /**
     * 最长公共子串问题 动态规划的到的二维表结果
     *
     * @param str1 字符串
     * @param str2 字符串
     * @return 二维矩阵
     */
    private static int[][] getdp(char[] str1, char[] str2) {
        int[][] dp = new int[str1.length][str2.length];

        // 初始化第0列
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str2[0]) {
                dp[i][0] = 1;
            }
        }
        // 初始化第0行
        for (int i = 0; i < str2.length; i++) {
            if (str1[0] == str2[i]) {
                dp[0][i] = 1;
            }
        }

        // 处理剩下的列和行
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                if (str1[i] == str2[j]) {
                    // 当前值只依赖左上角的值
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }

        return dp;
    }

    /**
     * 返回两个字符串的最长公共子串
     * 空间压缩版本的动态规划解法
     *
     * @param s1 字符串
     * @param s2 字符串
     * @return 最长公共子串
     */
    public static String leastCommonSubSubString2(String s1, String s2) {
        if (s1 == null || s2 == null || "".equals(s1) || "".equals(s2)) {
            return "";
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();

        // 斜线开始位置的行
        int row = 0;
        // 斜线开始位置的列
        int col = str2.length - 1;
        // t达到的全局最大值
        int max = 0;
        // 最长公共字串在s1中的结束位置
        int end = 0;

        int i;
        int j;
        int len;
        while (row < str1.length) {
            // 初始化开始点坐标和找到的最长公共字串长度
            i = row;
            j = col;
            len = 0;

            // 从起始点向右下角45走，走到最后一行跳出
            while (i < str1.length && j < str2.length) {
                if (str1[i] != str2[j]) {
                    len = 0;
                } else {
                    len++;
                }

                if (len > max) {
                    end = i;
                    max = len;
                }
                i++;
                j++;
            }

            if (col > 0) {
                // 起始点先向左移动
                col--;
            } else {
                // 起始点先向左移动，不能向左移动了就向下移动
                row++;
            }
        }

        return s1.substring(end - max + 1, end + 1);
    }
}
